/**
 * @Author: zqb
 * @Description: //TODO
 * @Date: Created in 11:46 2020/5/9
 * @Create By:
 */
public class Test {

    /**
     * 动态规划法
     * 子串是否为回文字符串呢？下面给出判断的公式，
     * <p>
     * 即动态规划的状态转移公式：
     * 给定字符串“s0s1 s2…sn”，
     * 假设
     * p（i，j）=1表示“si si+1…sj”是回文字符串；
     * p（i，j）=0则表示“si si+1…sj”不是回文字符串。
     * <p>
     * 那么：
     * <p>
     * p（i，i）=1如果si==si+1，则p（i，i+1）=1，否则p（i，i+1）=0。
     * 如果si+1==sj+1，则p（i+1，j+1）=p（i，j）。
     */

    private int center;
    private int palindromeLen;

    public int getCenter() {
        return center;
    }

    public void setCenter(int center) {
        this.center = center;
    }

    public int getPalindromeLen() {
        return palindromeLen;
    }

    public void setPalindromeLen(int palindromeLen) {
        this.palindromeLen = palindromeLen;
    }

    int min(int a, int b) {
        return a > b ? b : a;
    }

    /**
     * 方法功能：找出字符串最长的 回文子串
     * 输入参数:str为字符串，center回文字符的中心字符，len表示回文富川长度
     * 如果长度为偶数，center表示中间偏左边的那个字符的位置
     */
    void manacher(String str) {
        int len = str.length();//字符串长度
        int newLen = 2 * len + 1;
        char[] s = new char[newLen];//插入分隔符后的字符串
        int[] p = new int[newLen];
        int i;
        int id = 0;//id表示以第id个字符为中心的回文字符串 右端的下标值最大
        for (i = 0; i < newLen; i++) {
            //构造填充字符串
            s[i] = '*';
            p[i] = 0;
        }
        for (i = 0; i < len; i++) {
            s[(i + 1) * 2] = str.charAt(i);
        }
        center = -1;
        palindromeLen = -1;
        //求解p数组
        for (i = 0; i < newLen; i++) {
            if (id + p[id] > i) {
                p[i] = min(id + p[id] - 1, p[2 * id - i]);
            } else {
                p[i] = 1;
            }
            while (i + p[i] < newLen && i - p[i] > 0 && s[i - p[i]] == s[i + p[i]]) {
                p[i]++;
            }
            //当前就出的回文字符串最右端的下标更大
            if (i + p[i] > id + p[id]) {
                id = i;
            }
            if (p[i] - 1 > palindromeLen) {
                center = (i + 1) / 2 - 1;
                palindromeLen = p[i] - 1;//更新最长回文子串的长度
            }
        }
    }

    public static void main(String[] args) {
        String str = "abcbax";
        Test t = new Test();
        t.manacher(str);
        int center = t.getCenter();
        int palindromeLen = t.getPalindromeLen();
        if (center != -1 && palindromeLen != -1) {
            System.out.println("最长的回文子串为：");
            //回文字符串长度为奇数
            if (palindromeLen % 2 == 1) {
                for (int i = center - palindromeLen / 2; i <= center + palindromeLen / 2; i++) {
                    System.out.print(str.charAt(i));
                }
            } else {
                for (int i = center - palindromeLen / 2; i < center + palindromeLen / 2; i++) {
                    System.out.print(str.charAt(i));
                }
            }
        } else {
            System.out.println("查找失败");
        }
    }
}
